package com.wrial.offer;
/*
 * @Author  Wrial
 * @Date Created in 21:53 2020/4/2
 * @Description 青蛙跳台阶问题
 * 1.递归
 * 2.记忆化递归
 * 3.动态规划
 */

public class FaceTest_12_II {

    /**
     *  动态规划  f(n) = f(n-1)+f(n-2) 因为只能使用到三个空间就不需要给设立多余空间
     *  如果数字越界要进行处理
     */
    public int numWays(int n) {
        int a = 1;
        int b = 1;
        int sum = 0;
        for (int i = 2;i<=n;i++){
            sum = (a+b)%1000000007;
            b = a;
            // 把sum给a
            a = sum;
        }
        return a;

    }
}
